In a broad sense, the primary goal of a measurement can be defined as making a phenomenon available for human perception. Even when the results of measurements are used to automatically control machines and processes, the results of such control need to be meaningful, and thus the narrower technical meanings of a measurement still fall under the more general definition. In a technical sense, measurement often means finding a numerical expression of the value of a variable in relation to a unit or datum or to another variable of the same nature. This is normally accomplished by practical implementation of an idealized data acquisition system. The idealization is understood as a (simplified) model of such measuring process, which can be analyzed and comprehended by individuals. This analysis can either be performed directly through senses, or employ additional tools such as computers. When the measurement is reduced to a record, such record is normally expressed in discrete values in order to reduce the amount of information, and to enable storage of this record and its processing by digital machines. The reduction to a finite set of values is also essential for human comprehension. However, a physical embodiment of an idealized data acquisition system is usually an analog machine. That is, it is a machine with continuous action, where the components (mechanical apparatus, electrical circuits, optical devices, and so forth) respond to the input through the continuously changing parameters (displacements, angles of rotation, currents, voltages, and so forth). When the results of such implementation are reduced to numerical values, the uncertainties due to either limitations of the data acquisition techniques, or to the physical nature of the measured phenomenon, are often detached from these numerical values, or from each other. Ignoring the interdependence of different variables in the analyzed system, either intrinsic (due to their physical nature), or introduced by measuring equipment, can lead to misleading conclusions. An example of such idealization of a measurement is its digital record, where the measurement is represented by a finite set of numbers. It needs to be pointed out that the digital nature of a record is preserved even if such record were made continuous in time, that is, available as a (finite) set of instantaneous values.
Generally, measurement can be viewed as transformation of the input variable into another variable such that it can be eventually perceived, or utilized in some other manner. Measurement may consist of many intermediate steps, or stages between the incoming variable and the output of the acquisition system. For example, a TV broadcast can simplistically be viewed as (optical) measurement of the intensity of the light (incoming variable). where the output (image) is displayed on a TV screen. The same collectively would be true for a recorded TV program, although the intermediate steps of such a measurement will be different.
Regardless of the physical nature of measuring processes, they all exhibit many common features. Namely, they all involve transformation and comparison of variables at any stage. Transformation may or may not involve conversion of the nature of signals (for instance, conversion of pressure variations into electric signals by a microphone in acoustic measurements), and transformation can be either linear or nonlinear. Most transformations of variables in an acquisition system involve comparison as the basis for such transformations. Comparison can be made in relation to any external or internal reference, including the input variable itself. For example, simple linear filtering of a variable transforms the input variable into another variable, which is a weighted mean of the input variable either in time, space, or both. Here the comparison is made with the sample of the input variable, and the transformation satisfies a certain relation, that is, the output is the weighted average of this sample. An example of such filtering would be the computation of the Dow Jones Industrial Average.
In measurements of discrete events, a particular nonlinear filtering technique stands out due to its important role in many applications. This technique uses the relative positions, or rank, of the data as a basis for transformation. For example, the salaries and the family incomes are commonly reported as percentiles such as current median salary for a certain profession. The rationale for reporting the median rather than the mean income can be illustrated as follows. Consider some residential neighborhood generating ten million dollars annually. Now, if someone from this neighborhood wins twenty millions in a lottery, this will triple the total as well as the mean income of the neighborhood. Thus reporting the mean family income will create an illusion of a significant increase in the wealth of individual families. The median income, however, will remain unchanged and will reflect the economic conditions of the neighborhood more accurately. As another simple example, consider the way in which a student's performance on a standardized test such as the SAT (Scholastic Aptitude Test) or GRE (Graduate Record Examination) is measured. The results are provided as a cumulative distribution function, that is, are quoted both as a “score” and as the percentile. The passing criterion would be the score for a certain percentile. This passing score can be viewed as the output of the “admission filter”.
In digital signal processing, a similar filtering technique is commonly used and is referred to as rank order or order statistic filtering. Unlike a smoothing filter which outputs a weighted mean of the elements in a sliding window, a rank order filter picks up an output according to the order statistic of elements in this window. See, for example, Arnold et al., 1992, and Sarhan and Greenberg, 1962, for the definitions and theory of order statistics. Maximum, minimum, and median filters are some frequently used examples. Median filters are robust, and can remove impulse noise while preserving essential features. The discussion of this robustness and usefulness of median filters can be found in, for example, Arce et al., 1986. These filters are widely used in many signal and image processing applications. See, for example, Bovik et al., 1983; Huang, 1981; Lee and Fam, 1987. Many examples can be found in fields such as seismic analysis Bednar, 1983, for example, biological signal processing Fiore et al., 1996, for example, medical imaging Ritenour et al., 1984, for example, or video processing Wischermann, 1991, for example. Maximum and minimum selections are also quite common in various applications Haralick et al., 1987, for example.
Rank order filtering is only one of the applications of order statistic methods. In a simple definition, the phrase order statistic methods refers to methods for combining a large amount of data (such as the scores of the whole class on a homework) into a single number or small set of numbers that give an overall flavor of the data. See, for example, Nevzorov, 2001, for further discussion of different applications of order statistics. The main limitations of these methods arise from the explicitly discrete nature of their definition (see, for example, the definitions in Sarhan and Greenberg, 1962, and Nevzorov, 2001), which is in striking dissonance with the continuous nature of measurements. The discrete approach imposes the usage of algebraic rather than geometric tools in order statistics, and thus limits both the perception of the results through the geometric interpretation and the applicability of differential methods of analysis.
Order statistics of a sample of a variable is most naturally defined in terms of the cumulative distribution function of the elements composing this sample see David, 1970, for example, which is a monotonic function. Thus computation of an order statistic should be equivalent to a simple task of finding a root of a monotonic function. However, the cumulative distribution of a discrete set is a discontinuous function, since it is composed of a finite number of step functions (see Scott, 1992, for example). As a result, its derivative (the density function) is singular, that is, composed of a finite number of impulse functions such as Dirac δ-function (see, for example, Dirac, 1958, p. 58–61, or Davydov, 1988, p. 609–612, for the definition and properties of the Dirac δ-function). When implementing rank order methods in software, this discontinuity of the distribution function prevents us from using efficient methods of root finding involving derivatives, such as the Newton-Raphson method (see Press et al., 1992, and the references therein for a discussion of root finding methods). In hardware, the inability to evaluate the derivatives of the distribution function disallows analog implementation. Even though for a continuous-time signal the distribution function may be continuous in special cases (since now it is an average of an infinitely large number of step functions), the density function is still only piecewise continuous, since every extremum in the sample produces singularity in the density function (Nikitin, 1998, Chapter 4, for example). In fact, the nature of a continuous-time signal is still discrete, since its instantaneous and even time averaged densities are still represented by impulse functions (Nikitin, 1998, for example). Thus the time continuity of a signal does not automatically lead to the continuity of the distribution and the density, functions of a sample of this signal.
Following from their discrete nature, the limitations of the existing rank order methods (rank order filtering as well as other methods based on order statistics) can roughly be divided into two categories. The first category deals with the issues of the implementation of these methods, and the second one addresses the limitations in the applicability. The implementation of the order statistics methods can in turn be divided into two groups. The first group realizes these methods in software on sequential or parallel computers (see Juhola et al., 1991, for example). The second one implements them on hardware such as Very Large Scale Integration (VLSI) circuits (see Murthy and Swamy, 1992, for example).
In software implementation, the basic procedure for order statistics calculation is comparison and sorting. Since sorting can be constructed by selection, which is an operation linear in complexity, the algorithms for finding only a specific rank (such as median) are more effective than the algorithms for computation of arbitrary statistics (Pasian, 1988, for example). In addition, the performance of rank order calculations can be improved by taking advantage of the running window where only a minor portion of the elements are deleted and replaced by the same number of new elements (Astola and Campbell, 1989, for example). Regardless of the efficiency of particular algorithms, however, all of them quickly become impractical when the size of the sample grows, due to the increase all both computational intensity and memory requirements.
The hardware implementation of rank order processing has several main approaches, such as systolic algorithms (Fisher, 1984, for example), sorting networks (Shi and Ward, 1993, and Opris, 1996, for example), and radix (binary partition) methods (Lee and Jen, 1993, for example). The various hardware embodiments of the order statistics methods, however, do not overcome the intrinsic limitations of the digital approach arising from the discontinuous nature of the distribution function, such as inefficient rank finding, difficulties with processing large samples of data, and inability to fully explore differential techniques of analysis. It needs to be pointed out that the differential methods allow studying the properties “at a point”, that is, the properties which depend on an arbitrary small neighborhood of the point rather than on a total set of the discrete data. This offers more effective technical solutions. Several so-called “analog” solutions to order statistic filtering have been proposed see Jarske and Vainio, 1993, for example, where the term “analog” refers to the continuous (as opposed to quantized) amplitude values, while the time remains discrete. Although a definition of the continuous-time analog median filter has been known since the 1980's (see Fitch et al., 1986), no electronic implementations of this filter have been introduced. Perhaps the closest approximation of the continuous-time analog median filter known to us is the linear median hybrid (LMH) filter with active RC linear subfilters and a diode network (Jarske and Vainio, 1993, for example).
The singular nature of the density functions of discrete variables does not only impede both software and hardware implementations of rank order methods, but also constrains the applicability of these methods (for example, their geometric extension) to signal analysis. The origin of these constraints lies in the contrast between the discrete and the continuous: “The mathematical model of a separate object is the unit, and the mathematical model of a collection of discrete objects is a sum of units, which is, so to speak, the image of pure discreteness, purified of all other qualities. On the other hand, the fundamental, original mathematical model of continuity is the geometric figure; . . . ” (Aleksandrov et al., 1999, v. I, p. 32). Even simple time continuity of the incoming variable enables differentiation with respect to time, and thus expands such applicability to studying distributions of local extrema and crossing rates of signals (Nikitin et al., 1998, for example), which can be extremely useful characteristics of a dynamic system. However, these distributions are still discontinuous (singular) with respect to the displacement coordinates (thresholds). Normally, this discontinuity does not restrain us from computing certain integral characteristics of these distributions, such as their different moments. However, many useful tools otherwise applicable to characterization of distributions and densities are unavailable. For instance, in studies of experimentally acquired distributions the standard and absolute deviations are not reliable indicators of the overall widths of density functions, especially when these densities are multimodal, or the data contain so-called outliers. A well-known quantity Full Width at Half Maximum (FWHM) (e.g., Zaidel' et al., 1976, p. 18), can characterize the width of a distribution much more reliably, even when neither standard nor absolute deviation exists. The definition of FWHM, however, requires that the density function be continuous and finite. One can introduce a variety of other useful characteristics of distributions and density functions with clearly identifiable geometrical and physical meaning, which would be unavailable for a singular density function. An additional example would be an α-level contour surface (Scott, 1992, p. 22), which requires both the continuity and the existence of the maximum or modal value of the density function.
Discontinuity of the data (and thus singularity of density functions) is not a direct result of measurements but rather an artifact of idealization of the measurements, and thus a digital record should be treated simply as a sample of a continuous variable. For example, the threshold discontinuity of digital data can be handled by convolution of the density function of the discrete sample with a continuous kernel. Such approximation of the “true” density is well known as Kernel Density Estimates (KDE) (Silverman, 1986, for example), or the Parzen method (Parzen, 1967, for example). This method effectively transforms a digital set into a threshold continuous function and allows successful inference of “true” distributions from observed samples. See Lucy, 1974, for the example of the rectification of observed distributions in statistical astronomy. The main limitation of the KDE is that the method primarily deals with samples of finite size and does not allow treatment of spatially and temporally continuous data. For example, KDE does not address the time dependent issues such as order statistic filtering, and does not allow extension of the continuous density analysis to intrinsically time dependent quantities such as counting densities. Another important limitation of KDE is that it fails to recognize the importance of and to utilize the cumulative distribution function for analysis of multidimensional variables. According to David W. Scott (Scott, 1992, page 35), “. . . The multivariate distribution function is of little interest for either graphical or data analytical purposes. Furthermore, ubiquitous multivariate statistical applications such as regression and classification rely on direct manipulation of the density function and not the distribution function”. Some other weaknesses of KDE with respect to the present invention will become apparent from the further disclosure.
Threshold, spatial, and temporal continuity are closely related to our inability to conduct exact measurements, for a variety of reasons ranging from random noise and fluctuations to the Heisenberg uncertainty. Sometimes the exact measurements are unavailable even when the measured quantities are discrete. An example can be the “pregnant chad” problem in counting election votes. As another example, consider the measurement of the energy of a charged particle. Such measurement is normally carried out by means of discriminators. An ideal discriminator will register only particles with energies larger than its threshold. In reality, however, a discriminator will register particles with smaller energies as well, and will not detect some of the particles with larger energies. Thus there will be uncertainties in our measurements. Such uncertainties can be expressed in terms of the response function of the discriminator. Then the results of our measurements can be expressed through the convolution of the “ideal” measurements with the response function of the discriminator (Nikitin, 1998, Chapter 7, for example). Even for a monoenergetic particle beam, our measurements will be represented by a continuous curve. Since deconvolution is at least an impractical, if not impossible, way of restoring the “original” signal, the numerical value for the energy of the incoming particles will be deduced from the measured density curve as, for example, its first moment (Zaidel' et al., 1976, pp. 11–24, for example).
A methodological basis for treatment of an incoming variable in terms of its continuous densities can be found in fields where the measurements are taken by an analog action machine, that is, by a probe with continuous (spatial as well as temporal) impulse response, such as optical spectroscopy (see Zaidel' et al., 1976, for example). The output of such a measuring system is described by the convolution of the impulse response of the probe with the incoming signal, and is continuous even for a discrete incoming signal. For instance, the position of a certain spectral line measured by a monochromator is represented by a smooth curve rather than by a number. If the reduction of the line's position to a number is needed, this reduction is usually done by replacing the density curve by its modal, median, or average value.
The measurement of variables and analysis of signals often go hand-in-land, and the distinction between the two is sometimes minimal and normally well understood from the context. One needs to understand, however, that a “signal”, commonly, is already a result of a measurement. That is, a “signal” is already a result of a transformation (by an acquisition system) of one or many variables into another variable (electrical, optical, acoustic, chemical, tactile, etc.) for some purpose, such as further analysis, transmission, directing, warning, indicating, etc. The relationship between a variable and a signal can be of a simple type, such that an instantaneous value of the variable can be readily deduced from the signal. Commonly, however, this relationship is less easily decipherable. For example, a signal from a charged particle detector is influenced by both the energies of the particles and the times of their arrival at the sensor. In order to discriminate between these two variables, one either needs to use an additional detector (or change the acquisition parameters of the detector), or to employ additional transformation (such as differentiation) of the acquired signal. The analysis of the signal is thus a means for gathering information about the variables generating this signal, and ultimately making the phenomenon available for perception, which is the goal. The artificial division of this integral process into the acquisition and the analysis parts can be a serious obstacle in achieving this goal.
In the existing art, the measurement is understood as reduction to numbers, and such reduction normally takes place before the analysis. Such premature digitization often unnecessary complicates the analysis. The very essence of the above discussion can be revealed by the old joke that it might be hard to divide three potatoes between two children unless you make mashed potatoes. Thus we recognize that the nature of the difficulties with implementation and applicability of order statistics methods in analysis of variables lies in the digital approach to the problem. By digitizing, we lose continuity. Continuity does not only naturally occur in measurements conducted by analog machines, or arise from consideration of uncertainty of measurements. It is also important for perception and analysis of the results of complex measurements, and essential for geometrical and physical interpretation of the observed phenomena. The geometric representation makes many facts of analysis “intuitive” by analogy with the ordinary space. By losing continuity, we also lose differentiability, which is an indispensable analytical tool since it allows us to set up differential equations describing the studied system: “ . . . In order to determine the function that represents a given physical process, we try first of all to set up an equation that connects this function in some definite way with its derivatives of various orders” (Aleksanidrov et al., 1999, v. I, p. 119).
The origin of the limitations of the existing art can thus be identified as relying on the digital record in the analysis of the measurements, which impedes the geometrical interpretation of the measurements and leads to usage of algebraic rather than differential means of analysis.